`
https://leetcode.cn/problems/network-recovery-pathways/
`

/**
 * @param {number[][]} edges
 * @param {boolean[]} online
 * @param {number} k
 * @return {number}
 */
var findMaxPathScore = function (edges, online, k) {
  const n = online.length
  const g = Array.from({ length: n }, () => [])
  let maxWt = -1
  for (const [u, v, cost] of edges) {
    if (online[u] && online[v]) {
      g[u].push([v, cost])
      if (u === 0) maxWt = Math.max(maxWt, cost)
    }
  }

  // 给定下界 lower ，能否找到一条有效路径，除了满足题目要求，还满足路径上的边权都 >= lower
  const check = (lower) => {
    const memo = new Array(n).fill(-1)
    const dfs = (x) => {
      // 到达终点
      if (x === n - 1) return 0
      if (memo[x] !== -1) return memo[x]
      let res = Infinity
      for (const [to, cost] of g[x]) {
        if (cost >= lower) {
          res = Math.min(res, dfs(to) + cost)
        }
      }
      memo[x] = res
      return res
    }
    return dfs(0) <= k
  }

  let left = -1, right = maxWt + 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      left = mid
    } else {
      right = mid
    }
  }
  return left
};